// 0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字(删除后从下一个数字开始计数)。
// 求 出这个圆圈里剩下的最后一个数字。
//  例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1， 因此最后剩下的数字是3。

import ArrayQueue from './01.基于数组实现队列';

// 破冰游戏
// 社团共有 num 位成员参与破冰游戏，编号为 0 ~ num-1。
// 成员们按照编号顺序围绕圆桌而坐。
// 社长抽取一个数字 target，从 0 号成员起开始计数，排在第 target 位的成员离开圆桌，且成员离开后从下一个成员开始计数。
// 请返回游戏结束时最后一位成员的编号。
// 示例 1：输入：num = 7, target = 4 输出：1
// 示例 2：输入：num = 12, target = 5 输出：0

function lastRemaining(num: number, target: number) {
  const queue = new ArrayQueue<number>();
  for (let i = 0; i < num; i++) {
    queue.enqueue(i);
  }
  while (queue.size > 1) {
    for (let i = 1; i < target; i++) {
      //   const n = queue.dequeue();
      //   if (n) queue.enqueue(n);

      queue.enqueue(queue.dequeue()!);
    }
    queue.dequeue()!;
  }
  return queue.dequeue()!;
}

console.log(lastRemaining(7, 4)); // 1
console.log(lastRemaining(12, 5)); // 0
console.log(lastRemaining(5, 3)); // 3
